package Other.DP;

/**
 * @author:gao
 * @date:2020/7/11
 * @time:18:49
 * @version:0.0.1
 * @description:none
 */

//53. 最大子序和
public class Five_MaxSubArray {
}

//dp+优化
class SolutionFive008 {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        int pre =nums[0];
        int max =pre;
        for(int i=1;i<nums.length;i++){
            //dp i = max ( dp i-1 + nums[i] ,nums[i]   )
            pre = Math.max(pre+nums[i],nums[i]);
            max=max>pre?max:pre;
        }
        return max;
    }
}


//直接相加
class SolutionFive0000{
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int max= nums[0];
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            if(sum < 0){
                sum = 0;
            }
            sum += nums[i];
            max = Math.max(max, sum);

        }
        return max;
    }
}